package com.lun.swordtowardoffer2.c10;

import java.util.List;

import com.lun.swordtowardoffer2.c10.Trie.TrieNode;

public class ReplaceWords {

	private TrieNode buildTrie(List<String> dict) {
		TrieNode root = new TrieNode();
		for(String word : dict) {
			TrieNode node = root;
			
			for(char ch : word.toCharArray()) {
				int index = ch - 'a';
				
				if(node.children[index] == null) {
					node.children[index] = new TrieNode();
				}
				
				node = node.children[index];
			}
			node.isWord = true;
		}
		return root;
	}
	
	private String findPrefix(TrieNode root, String word) {
		TrieNode node = root;
		StringBuilder sb = new StringBuilder();
		for(char ch : word.toCharArray()) {
			int index = ch - 'a';
			if(node.isWord || node.children[index] == null) {
				break;
			}
			sb.append(ch);
			node = node.children[index];
		}
		
		return node.isWord ? sb.toString() : "";
	}
	
	public String replaceWords(List<String> dict, String sentence) {
		TrieNode root = buildTrie(dict);
		
		String[] words = sentence.split(" ");
		
		for(int i = 0; i < words.length; i++) {
			String prefix = findPrefix(root, words[i]);
			if(!prefix.isEmpty()) {
				words[i] = prefix;
			}
		}
		
		return String.join(" ", words);
	}
	
}
